// easy

// 设计一个栈，实现push，pop，top, getMin操作，其中getMin要求能在常数时间内实现

// 思路：由于getMin常数时间，所以我们应该在push和pop的时候就已经计算好最小值
// 思路1： 辅助栈
// 使用辅助栈保存当前栈中的最小值，在元素入栈出栈时，两个栈同步保持插入和删除

// 时间复杂度：O(1)
// 空间复杂度：O(n)

class MinStack2 {
    constructor() {
        this.stack = []
        this.minStack = []
    }

    push(val) {
        if (!this.stack.length) {
            this.stack.push(val)
            this.minStack.push(val)
        } else {
            this.stack.push(val)
            this.minStack.push(Math.min(val, this.minStack[this.minStack.length - 1]))
        }
    }

    pop() {
        this.stack.pop()
        this.minStack.pop()
    }

    top() {
        return this.stack[this.stack.length - 1]
    }

    getMin() {
        return this.minStack[this.minStack.length - 1]
    }
}

function Node(x) {
    this.val = x
    this.min = x
}
function MinStack() {
    this.stack = []
}

MinStack.prototype.push = function (val) {
    let node = new Node(val)
    if (this.stack.length) {
        let topNode = this.stack[this.stack.length - 1]
        if (node.min > topNode.min) {
            node.min = topNode.min
        }
    }
    this.stack.push(node)
};

MinStack.prototype.pop = function () {
    this.stack.pop()
};

MinStack.prototype.top = function () {
    return this.stack[this.stack.length - 1].val
};

MinStack.prototype.getMin = function () {
    return this.stack[this.stack.length - 1].min
};